package leetcode.day_2020_12_21_12_28;

import com.sun.java.swing.plaf.windows.WindowsTextAreaUI;
import com.sun.org.apache.bcel.internal.generic.FSUB;

import java.util.*;

/**
 * 78. 子集
 */
public class L_78 {
    static List<Integer> t = new ArrayList<>();
    static List<List<Integer>> res = new ArrayList<>();
    static Vector<Vector<Integer>> res2 = new Vector<>();

    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        System.out.println(subsets5(arr));
    }

    /**
     * 递归 1
     * @param nums
     * @return
     */
    public static List<List<Integer>> subsets(int[] nums) {
        // base case
        if (nums.length == 0) {
            List list = new ArrayList();
            list.add(new ArrayList<>());
            return list;
        }
        // 把数组最后一个元素拿出来
        int n = nums[nums.length-1];
        int[] newNums = Arrays.copyOf(nums, nums.length-1);

        // 先递归算出前面元素的所有子集
        List<List<Integer>> res = subsets(newNums);

        int size = res.size();

        for(int i=0; i<size; i++) {
            List demo = new ArrayList();
            for(int j=0; j<res.get(i).size(); j++) {
                demo.add(res.get(i).get(j));
            }
            // 然后再之前的结果上追加
            demo.add(n);
            res.add(demo);
        }
        return res;
    }

    /**
     * 递归 2
     * @param nums
     * @return
     */
    public static List<List<Integer>> subsets2(int[] nums) {
        return recurse(nums.length, nums);
    }

    public static List<List<Integer>> recurse(int cur, int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if(cur == 0) {
            // 空集
            result.add(new ArrayList<>());
            return result;
        }

        List<List<Integer>> existing_result = recurse(cur-1, nums);
        result.addAll(existing_result);
        for(List<Integer> subset : existing_result) {
            List<Integer> newSubset = new ArrayList<>(subset);
            newSubset.add(nums[cur-1]);
            result.add(newSubset);
        }
        return result;
    }

    /**
     * 回溯 1
     * @param nums
     * @return
     */
    public static List<List<Integer>> subsets3(int[] nums) {
        backtrack(0, nums);
        return res;
    }

    public static void backtrack(int start, int[] nums) {
        if(start == nums.length) {
            res.add(new ArrayList<>(t));
            return;
        }
        t.add(nums[start]);
        backtrack(start+1, nums);
        t.remove(t.size() - 1);
        backtrack(start+1, nums);
    }

    /**
     * 回溯 2
     * @param nums
     * @return
     */
    public static List<List<Integer>> subsets4(int[] nums) {
        // 记录走过的路径
        List<Integer> track = new ArrayList<>();
        backtrack2(nums, 0, track);
        return res;
    }

    public static void backtrack2(int[] nums, int start, List<Integer> track) {
        res.add(track);
        for(int i=start; i< nums.length; i++) {
            // 做选择
            List<Integer> newTrack = new ArrayList<>(track);
            newTrack.add(nums[i]);
            // 回溯
            backtrack2(nums, i+1, newTrack);
            // 撤销选择
            newTrack.remove(newTrack.size()-1);
        }
    }

    public static Vector<Vector<Integer>> subsets5(int[] nums) {
        Vector<Integer> track = new Vector<>();
        backtrack3(nums, 0, track);
        return res2;
    }

    public static void backtrack3(int[] nums, int start, Vector<Integer> track) {
        res.add(track);
        for(int i=start; i< nums.length; i++) {
            track.add(nums[i]);
            backtrack3(nums, i+1, track);
            track.remove(track.size()-1);
        }
    }
}
